'''
https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph
'''
from typing import List

class UF:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.sets = n
    def find(self, x):
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]
    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx != fy:
            self.father[fy] = fx
            self.sets -= 1

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UF(n)
        for u, v in edges:
            uf.union(u, v)
        return uf.sets